package com.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 1074. 元素和为目标值的子矩阵数量
 * <p>
 * 给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。
 * 子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。
 * 如果 (x1, y1, x2, y2) 和 (x1', y1', x2', y2') 两个子矩阵中部分坐标不同（如：x1 != x1'），那么这两个子矩阵也不同。
 */
public class LeetCode1074 {

    public static void main(String[] arg0) {
        int[][] matrix = new int[3][3];
        matrix[0][0] = 0;
        matrix[0][1] = 1;
        matrix[0][2] = 0;
        matrix[1][0] = 1;
        matrix[1][1] = 1;
        matrix[1][2] = 1;
        matrix[2][0] = 0;
        matrix[2][1] = 1;
        matrix[2][2] = 0;
        System.out.println("(target = 0) size = " + numSubmatrixSumTarget(matrix, 0));
    }

    public static int numSubmatrixSumTarget(int[][] matrix, int target) {
        int num = 0;
        int width = matrix.length;
        int height = matrix[0].length;
        for (int i = 0; i < width; i++) { // 枚举上边界
            int[] sum = new int[height];
            for (int j = i; j < width; j++) { // 枚举下边界
                for (int k = 0; k < height; k++) {
                    sum[k] += matrix[j][k];
                }
                System.out.println("sum array: " + Arrays.toString(sum));
                num += subArraySum(sum, target);
            }
        }
        return num;
    }

    /**
     * 不明觉厉
     */
    public static int subArraySum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>(); // 这里的键是一个和值，值是这个和值出现的次数。
        map.put(0, 1);
        int count = 0, pre = 0;
        for (int num : nums) {
            pre += num;
            System.out.print(pre + ", ");
            if (map.containsKey(pre - target)) {
                count += map.get(pre - target);
            }
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        System.out.println("。");
        return count;
    }

    /**
     * 求一个矩阵所有元素的和
     */
    public static int subMatrixSum(int[][] subMatrix) {
        int sum = 0;
        int width = subMatrix.length;
        int height = subMatrix[0].length;
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++) {
                sum += subMatrix[i][j];
            }
        }
        return sum;
    }

}
